/*
 * The RavenX Library
 * Copyright (c) 2008 by Solidus
 * 
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.It is provided "as is" without express 
 * or implied warranty.
 *
 */

#ifndef RX_RBTREE_H
#define RX_RBTREE_H

#include "rx_typedef.h"



RX_SPACE_BEG

typedef struct __rx_rbtree_node_tag		rx_rbtree_node_t;

typedef struct __rx_rbtree_tag			rx_rbtree_t;


RavenAPI rx_rbtree_node_t* rx_rbtree_previous(rx_rbtree_node_t *node);
RavenAPI rx_rbtree_node_t* rx_rbtree_successor(rx_rbtree_node_t *node);

RavenAPI void*			   rx_rbtree_node_data(rx_rbtree_node_t *node);

RavenAPI rx_rbtree_node_t* rx_rbtree_leftmost(rx_rbtree_t *self);
RavenAPI rx_rbtree_node_t* rx_rbtree_rightmost(rx_rbtree_t *self);



RavenAPI rx_rbtree_t*	rx_rbtree_create(const rx_info_t *info, const rx_alloc_t *palloc);
RavenAPI void			rx_rbtree_destroy(rx_rbtree_t *self);
RavenAPI size_t			rx_rbtree_size(const rx_rbtree_t *self);
RavenAPI rx_rbtree_t*	rx_rbtree_copy(const rx_rbtree_t *self);

RavenAPI rx_rbtree_node_t* rx_rbtree_insert_unique(rx_rbtree_t *self, const void *data);
RavenAPI rx_rbtree_node_t* rx_rbtree_insert_equal(rx_rbtree_t *self, const void *data);

RavenAPI rx_rbtree_node_t* rx_rbtree_erase_node(rx_rbtree_t *self, rx_rbtree_node_t *node);
RavenAPI rx_rbtree_node_t* rx_rbtree_erase_range(rx_rbtree_t *self, rx_rbtree_node_t *first, rx_rbtree_node_t *last);

RavenAPI size_t	rx_rbtree_erase_key(rx_rbtree_t *self, const void *key);

RavenAPI void	rx_rbtree_clear(rx_rbtree_t *self);

RavenAPI rx_rbtree_node_t* rx_rbtree_find(rx_rbtree_t *self, const void *key);
RavenAPI rx_rbtree_node_t* rx_rbtree_lower_bound(rx_rbtree_t *self, const void *key);
RavenAPI rx_rbtree_node_t* rx_rbtree_upper_bound(rx_rbtree_t *self, const void *key);
RavenAPI size_t			 rx_rbtree_node_count(const rx_rbtree_t *self, const void *key);

RavenAPI void rx_rbtree_map(rx_rbtree_t *self, void (*oper_f)(void*));


/**********************************************utility**********************/
typedef struct __rx_rbtree_node_range_tag
{
		rx_rbtree_node_t		*first;
		rx_rbtree_node_t		*last;
}rx_rbtree_range_t;

RavenAPI rx_rbtree_range_t rx_rbtree_find_range(rx_rbtree_t *self, const void *key);



#if defined(RX_DEBUG)


RavenAPI void rx_rbtree_print(const rx_rbtree_t *self, rx_print_func_t print_f, rx_trace_func_t trace_f);

RavenAPI rx_bool rx_rbtree_verify(const rx_rbtree_t *self);

#else

#define rx_rbtree_print RX_NOOP


#define rx_rbtree_verify RX_NOOP



#endif




RX_SPACE_END


#endif

